package com.xiaoyu.bitOperation;

/**
 * @program: DS_and_A
 * @description: 自己想做的算法
 *
 * 有定理 ---> 设a，b为两个二进制数，则a+b = a^b + (a&b)<<1。
 *                                  a^b计算无进位和 ,(a&b)计算进位,然后左移让进位在它应该在的地方
 *
 *
 * 定理1：设a，b为两个二进制数，则a+b = a^b + (a&b)<<1。
 *      证明：a^b是不考虑进位时加法结果。当二进制位同时为1时，才有进位，
 *      因此 (a&b)<<1是进位产生的值，称为进位补偿。将两者相加便是完整加法结果。
 *
 * 定理2：使用定理1可以实现只用位运算进行加法运算。
 *      证明：利用定理1中的等式不停对自身进行迭代。每迭代一次，进位补偿右边就多一位0，
 *      因此最多需要加数二进制位长度次迭代，进位补偿就变为0，这时运算结束。
 * @author: YuWenYi
 * @create: 2021-05-12 15:09
 **/
public class BinaryAdd {


    public static Integer twoBinaryAdd(int a,int b){
        int sum = a^b;    //计算没有进位的和
        int carry = (a&b)<<1;  //计算进位的值
        //System.out.println(sum);
        //System.out.println(carry);
        return sum + carry;  //进位和无进位和相加,就是答案
    }

    public static Integer twoBinaryAddWithRecus(int a,int b){
        int sum = a^b;    //计算没有进位的和
        int carry = (a&b)<<1;  //计算进位的值
        System.out.println(sum);
        System.out.println(carry);
        return carry == 0 ? sum : twoBinaryAddWithRecus(sum,carry);
    }

    public static Integer multiBinaryAdd(int[] nums){
        int sum = 0;
        for (int num : nums) {
            //int carry = (sum&num)<<1;
            //int noCarrySum = sum^num;
            sum = ((sum&num)<<1) + (sum^num);
        }

        return sum;
    }


    public static void main(String[] args) {
        //100 ^ 100 --> 000   (100 & 100) << 1 --> 1000
        System.out.println(twoBinaryAddWithRecus(54, 25));

        //int[] a = new int[]{1,2,3,4,5,6,7,8,9,10,100};
        //System.out.println(multiBinaryAdd(a));

    }

}
